package pers.qianyu.month_202101.date_20210123;

/**
 * 二分算法解题步骤
 * 1. 确定二分的边界
 * 2. 编写二分代码的框架
 * 3. 设计一个性质，检查中点位于哪个部分
 * 4. 判断区间如何更新
 * 5. 如果更新方式为：left = mid, right = mid - 1的话，算mid的时候要 +1
 * <p>
 * 69. x 的平方根
 * https://leetcode-cn.com/problems/sqrtx/
 *
 * @author mizzle rain
 * @date 2021-01-23 15:46
 */
public class MySqrt {
    public int mySqrt(int x) {
        int left = 0, right = x;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (mid <= x / mid) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
